<?php
/**
 * Created by helloJiu.
 * Idea: 认真编码 快乐生活
 * Date: 2020/12/27
 * Time: 10:35
 */

namespace App\UnionFind;

/**
 * 数组实现并查集
 * Class AbsUnionFind
 * @package App\UnionFind
 */
class AbsUnionFind
{
    /**
     * 索引存元素, 值存元素的父节点
     * @var array
     */
    protected $data;

    protected $map;

    /**
     * AbsUnionFind constructor.
     * @param $data 需要加入并查集的所有元素数据, 元素需要能转成string, 对象的话, 需要实现toString()
     */
    public function __construct($data)
    {
        $this->data = [];
        foreach ($data as $v) {
            $s_v = strval($v);
            $this->data[$s_v] = $s_v;
            $this->map[$s_v] = $v;
        }
    }

    /**
     * 查找顶级节点
     * @param $v
     */
    public function find($v)
    {
    }

    /**
     * 合并节点
     * @param $v1
     * @param $v2
     */
    public function union($v1, $v2)
    {
    }

    protected function checkOutOfBound($v){
        if(empty($this->data[strval($v)])){
            throw new \OutOfBoundsException('下标越界');
        }
    }

    public function isSame($v1, $v2){
        return $this->find($v1) == $this->find($v2);
    }

    public function getData(){
        return $this->data;
    }

    /**
     * 加入新元素
     * @param $v
     */
    public function join($v){
        $s_v = strval($v);
        if(isset($this->data[$s_v])){
            return;
        }
        $this->data[$s_v] = $s_v;
        $this->map[$s_v] = $v;
    }


}